package leetcode.editor.cn.q1_300.q150;

import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author qidi
 * @date 2022-02-11 10:22:21
 */
class Q0173_BinarySearchTreeIterator {

    //leetcode submit region begin(Prohibit modification and deletion)
    class BSTIterator {

        Deque<TreeNode> stack = new ArrayDeque<>();

        public BSTIterator(TreeNode root) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
        }

        public int next() {
            TreeNode node = stack.pop();
            TreeNode cur = node.right;
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            return node.val;
        }

        public boolean hasNext() {
            return !stack.isEmpty();
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
//        BSTIterator bSTIterator = new BSTIterator(BTreeUtil.getInstance().generateFromArray(7, 3, 15, null, null, 9, 20));
//        System.out.println(bSTIterator.next()); // 返回 3
//        System.out.println(bSTIterator.next()); // 返回 7
//        System.out.println(bSTIterator.hasNext()); // 返回 True
//        System.out.println(bSTIterator.next()); // 返回 9
//        System.out.println(bSTIterator.hasNext()); // 返回 True
//        System.out.println(bSTIterator.next()); // 返回 15
//        System.out.println(bSTIterator.hasNext()); // 返回 True
//        System.out.println(bSTIterator.next()); // 返回 20
//        System.out.println(bSTIterator.hasNext()); // 返回 False
    }
}